1. Field of the Invention
The present invention relates in general to the field of the generation of sequences and, in particular, the generation of sequences of items from a database such that the relationship between the attributes of the component items in the sequence is controlled.
It is to be understood that in the present description the term  less than  less than database greater than  greater than  is used to designate any collection of data, for example covering both pre-stored data and data which is dynamically collected.
There are many situations in which it is necessary or desirable to create a sequence of items from a collection of items for which data is available, and it is important that the created sequence should be  less than  less than coherent greater than  greater than , that is, that there should be a particular relationship between attributes of the component items in the sequence (typically involving a criterion that the attributes of the component items of the sequence should not be too dissimilar, especially for successive items in the sequence). The sequences in question include temporal sequences and spatial sequences. A typical case where this problem arises is in the field of multimedia and, notably, the problem of automatic generation of recitals (such a recital is an example of a temporal sequence). Here the term  less than  less than recital greater than  greater than  is used not only to designate a sequence of musical pieces but, more generally, any temporal sequence of multimedia items (film clips, documentaries, text items, etc.). An example of a problem involving a spatial sequence concerns the designing of a thematically-linked layout of paintings for rooms in an art gallery.
2. Description of the Prior Art
It has been proposed in the paper  less than  less than Rxc3xa9presentation de sxc3xa9quences dxc3xa9finies sur des ensembles non instancixc3xa9s par arbre PQR partiel greater than  greater than  by Berkaoui et al [Journxc3xa9es Francophones de Programmation Logique par Contraintes, 1998] to use a Constraint Satisfaction approach for solving scheduling problems. However, the approach proposed in this paper does not consider the  less than  less than coherence greater than  greater than  of the sequence of items which is produced, notably it does not enable the similarity or dissimilarity of items making up the sequence to be controlled.
The present invention provides a system and method which produces  less than  less than coherent greater than  greater than  sequences of items in a particular order. The items are, generally, stored in a database and described in terms of data pairs each consisting of an attribute and the corresponding value. The problem of creating the desired sequence is treated as a Constraint Satisfaction Problem (CSP). The sequence to be obtained is specified by formulating a collection of constraints holding on items in the database, each constraint describing a particular property of the sequence. The sequence can be specified by any number of constraints.
According to the present invention, the items in the database exhibit a particular generic format with associated taxonomies for at least some of the attribute values. Also, the constraints are specified out of a predetermined library of generic constraint classes which have been specially formulated. The special constraint classes used in the present invention allow the expression of desired properties of the target sequence, notably properties of similarity between groups of items, properties of dissimilarity, and properties of cardinality. These constraint classes enable the properties of coherent sequences to be expressed in a particularly simple manner.
It is the combination of the use of a generic format for items in the database and the special constraint classes which enables the preferred embodiments of the present invention to use CSP solution techniques to solve the difficult combinatorial problem of building an ordered collection of elements satisfying a number of constraints.